package com.hyb.algorithm.data.struct.dp;

/**
 * 63. 不同路径 II
 * https://leetcode.cn/problems/unique-paths-ii/description/
 *
 * @author: ybhu
 * @create: 2024/01/04 19:28
 */
public class UniquePathsWithObstacles {

    public static void main(String[] args) {
        int[][] obstacleGrid = {{0, 0,0},{1, 0,0},{0, 0,0}};

        int ret = new UniquePathsWithObstacles().uniquePathsWithObstacles(obstacleGrid);

        System.out.println(ret);


    }

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid.length, m = obstacleGrid[0].length;

        //滚动数组 m 为列    n 为行
        //因为 它是按行累加的 所以 用一行压缩就行
        //i 从【0...n】
        // f[0]+f[1]+f[2]+....f(m)
        int[] f = new int[m];

        //初始化第一个元素  对于第j=0列 ，只要走到[i][0]=1的时候，那么f[0] 就永远为0 了 因为j-1>0 永远不会成立了
        f[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (obstacleGrid[i][j] == 1) {
                    f[j] = 0;
                    continue;
                }
                if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {
                    f[j] += f[j - 1];
                }
            }
        }

        return f[m - 1];
    }
}
